1. Technical Field
The present invention relates in general to integrated circuit design methods and in particular to a design method for buffer insertion within integrated circuits. Still more particularly, the present invention relates to a method of optimal segmentation of circuits for improved buffer insertion.
2. Description of the Related Art
Often, transistors are utilized in digital logic circuits to supply or "drive" many other transistors with logic signals. If transistors require interconnection and they are not adjacent on an integrated circuit, then they are interconnected utilizing wires. When the distance from a driving transistor or "source" to a receiving transistor or "sink" becomes long enough to adversely effect the signal propagation time, the interconnecting wire can be referred to as a "long wire". The propagation delay of a signal, due to long wires and multiple sinks, can be reduced by "repowering" or relaying the signal utilizing simple amplifiers, called buffers.
A single source driving many sinks creates a "fanout" circuit. Fanout circuits are commonly referred to as a "tree structure" or a "fanout tree". A fanout tree has detrimental loading characteristics on a propagating signal, particularly when one "branch" of a fanout tree becomes more populated or more heavily loaded than another "branch".
The intermix of capacitance and resistance in a fanout tree creates a resistive-capacitive (RC) time constant which retards the propagation of a signal. A major factor in reduced propagation speed is the resistive effects of long wires in conjunction with transistor gate capacitance.
The resistance (r) of a wire increases linearly as a function of wire length (l) and, the resistivity (R) of the material utilized, where r=Rl. Likewise, the capacitance of a wire (c) increases linearly with its length (l) and associated physical properties. Capacitance can be defined by c=Cl. Therefore, the "RC" delay (D) of a wire due to resistance and capacitances is D=1/2RCl.sup.2. As depicted by the l.sup.2 term, the delay due to the capacitive and resistive effects increases quadratically with the length of a wire. As the scale of integrated circuits and clock speeds continues to increase, timing difficulties associated with wire lengths have become a vexing problem.
In designing an integrated circuit, the physical layout is accomplished in view of all the pertinent design constraints. Generally, after the layout or geographical planning of a semiconductor chip is complete, buffer insertion is then addressed or considered. Development of faster and larger integrated circuits has created the need for effective and efficient computer aided design (CAD) tools. The most desirable computer assistance comes in the form of calculations on circuits to identify potential problems such as unacceptable delays. An area of integrated circuit design which has received additional attention recently is the prediction of unacceptable delays in high frequency digital circuits. The rapid development of higher clock frequencies has intensified the effort to develop CAD assistance.
In digital circuits, fanout trees having more than five sinks are common. Although each sink has a relatively small RC time constant, the cumulative effect of many sinks can create excessive delays. Propagation delays caused by excessive wire length can be reduced to a substantially linear relationship by introducing buffers at strategic intervals. Currently, designers of digital circuits are striving for clock frequency of one giga-hertz. Therefore, implementation of an optimum buffer topology in tree structures has become critical to minimize delays. Rapid advances in transistor technology have reduced delay problems associated with transistors switching, but the wires interconnecting the transistors have become the limiting factor for implementing increased clock speeds.
Accurate computing of a propagation delay within a wiring tree is difficult because it requires a solution for a set of differential equations. The set of differential equations arise from distributed RC combinations. For optimum solutions, variables such as wire size are altered, then the delay is recalculated. However, optimization can be very time consuming. Deriving estimates for circuit delay, by making assumptions for certain variables can be a more economical approach.
Many CAD delay calculations utilize the "Elmore" delay model. The Elmore delay model is named after the works of W. C. Elmore. The basis of the Elmore model can be found in an article entitled "The Transient Response of Damped Linear Networks with Particular Regard to Wide-Band Amplifiers," W. C. Elmore J. Appl. Phys., vol. 1, no 1, pp. 55-63, January 1948. The Elmore model has been utilized extensively for buffer insertion design aid because it is conducive to utilizing a hierarchical algorithm. A popular Elmore model utilizes a hierarchical algorithm which follows a general two phase bottom-up prediction and top-down decision approach. Another important factor in utilizing the Elmore model, is that the complexity of computing the number of possible buffer positions is linear and therefore the calculation can be performed efficiently. The Elmore delay theory has been widely utilized by CAD developers for computer aided insertion of buffers into circuits.
For example, "Buffer Placement in Distributed RC-Tree Networks for Minimal Elmore Delay", by L. P. P. P. van Ginneken, Proc. Intern.times.l Symposium on Circuits and Systems, 1990, pp. 865-868, proposed a solution for buffer insertion to minimize delay. Van Ginneken's method is severely limited because only one buffer can be placed on a single wire. This leads to solutions which have an inadequate quantity of buffers in most designs. For example, a fanout tree which requires three buffers for optimum performance will receive only one buffer utilizing van Ginneken's methods. Further, the device library of van Ginneken's proposal includes only one non-inverting buffer. A single device library also severely limits the effectiveness of the van Ginneken method by limiting candidate solutions.
An attempt to enhance the approach taken by Elmore and van Ginneken was presented in "Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model" by J. Lillis, C. -K. Chen and T. -T. Y. Lin, IEEE Journal of Solid State Circuits, 31(3), 1996, pp. 437-447. Here after referred to as Lillis. Lillis proposed subdividing wires into infinitesimally small segments. This approach allows an infinite number of buffer insertion topologies or solutions to be considered because a large quantity of buffers can be inserted on a given wire.
Lillis proposed many improvements to van Ginneken's approach, adding the functionalities of wire sizing, a non-unit buffer library and inverting buffers. The Lillis approach also incorporated slew into the gate delay calculation. Lillis subdivided wires into infinitesimally small segments to overcome the onerous problem of van Ginneken that only one buffer can be inserted on each wire. However, in utilizing the Lillis method, the processing speed for each wire becomes inordinately slow due to the endless topologies which must be considered by the CAD system. Therefore, the processing speed utilizing the Lillis method, on a given tree is too slow and inefficient for most applications. However, the Lillis approach provides many enhancements and an improved solution to the van Ginneken method. Again, the Lillis' model is too slow and inefficient for most applications.
Generally, in the design of integrated circuits, a proposed layout, a proposed change, or a design iteration requires a timing analysis or a timing reevaluation. A twenty minute computation for a CAD system to verify proper operation after a proposed change, renders a program unacceptable to most designers. For example, the approach of Lillis could take several days to process 10,000 fanout trees. On a modern integrated circuit, such as a microprocessor, implementing 10,000 fanout trees in the design of an integrated circuit is not uncommon.
Circuits having large RC time constraints require multiple buffers to effectively decouple the RC load. Judicious insertion of buffers into a single circuit path having critical timing can improve the timing performance of a circuit by several nano-seconds. As integrated circuits become larger and chip area becomes cheaper, high frequency operation has been the focus of integrated circuit designers. Efforts to increase the clock speeds of digital circuits have revealed the importance of automated buffer insertion tools. Automating buffer insertion with the aid of the computer saves the designer many weeks of tedious work. Timely computation of optimum buffer insertion is also required to evaluate design tradeoffs. Hence, finding the optimum number of buffers efficiently, is desirable and advantageous. Both efficiency and effectiveness are essential in a useful buffer insertion design tool.
Hence, there is a need for an effective and efficient design tool for efficiently and effectively segmenting wires prior to buffer insertion. The present invention is directed at solving the inefficiency and ineffectiveness of available buffer insertion design tools.